home *** CD-ROM | disk | FTP | other *** search
/ TPUG - Toronto PET Users Group / TPUG Users Group CD / TPUG Users Group CD.iso / AMIGA / AMICUS / AMICUS02.ADF / Asm / trees.doc < prev    next >
Text File  |  1989-05-30  |  4KB  |  77 lines
  1.  
  2. Documentation for the Unix System V functions tsearch(), tdelete(), and
  3. twalk() ported to the Commodore Amiga.  Object is in the file trees.o and
  4. can be linked with a C or assembler program.
  5. This document is formatted in a style similar to the Unix System V programmers
  6. manual.
  7.  
  8. Name:
  9.    tsearch, tdelete, twalk - manage binary trees.
  10.  
  11. Synopsis:
  12. extern   char *tsearch((char *) key, (char **)rootpntr, compar)
  13.          int (*compar) ();
  14.  
  15. extern   char *tdelete((char *) key, (char **)rootpntr, compar)
  16.          int (*compar)();
  17.  
  18. extern   void twalk((char *)rootp,action)
  19.          void (*action)();
  20.  
  21. Description:
  22.    tsearch is a binary tree search routine.  It returns a pointer into a tree
  23.    indicating where a datum may be found.  If the datum does not occur in the
  24.    tree it is added at an appropriate point in the tree.
  25.    Argument description:  KEY points to the datum to be sought in the tree.
  26.    ROOTPNTR points to a variable that points to the root of the tree (Notice
  27.    the double indirection here.)  A NULL pointer value for the variable
  28.    denotes an empty tree; in this case, the variable will be set to point to
  29.    the datum at the root of the new tree.  Compar is the name of the user
  30.    provided comparison function.  It is called with two arguments that point
  31.    to the elements being compared.  The function must return an integer less
  32.    than, equal to, or greater than zero signifying that the first argument is
  33.    less than, equal to, or greater than the second.  Compar need not compare
  34.    every byte in each argument so that the arguments may be structures
  35.    containing arbitrary data in addition to the key itself.  (See qtest.c for
  36.    an example of how to write a comparison function.)
  37.  
  38.    tdelete deletes a node from a binary tree.  The arguments are the same as
  39.    for tsearch.  The variable pointed to by the ROOTPNTR will be changed if
  40.    the deleted node was the root of the tree.  tdelete returns a pointer to
  41.    the parent of the deleted node, or a NULL pointer if the node is not found.
  42.  
  43.    twalk traverses a binary search tree.  ROOTP is the root of the tree to
  44.    be traversed.  (Any node in a tree may be used as the root for a walk
  45.    below that node.)  ACTION is the name of a routine to be invoked at each
  46.    node. This routine is, in turn, called with three arguments.  The first
  47.    argument is the address of the node being visited.  The second argument
  48.    is a value from an enumeration data type
  49.      typedef  enum {preorder, postorder, endorder, leaf} VISIT;
  50.    depending on whether this is the first, second, or third time that the
  51.    node has been visited (during a depth-first, left-to-right traversal of
  52.    the tree), or whether the node is a leaf.  (If enumeration types are not
  53.    available, use an int as the argument type and the values will be 
  54.    respectively {0,1,2,3}.  The third argument to ACTION is the level of
  55.    the node in the tree, with the root node being level 0.
  56. ** ACTION should be declared extern before it is defined to ensure proper
  57.    ordering of the arguments passed to it.  This is needed for Lattice C
  58.    on the Amiga which expects the arguments in left to right order if the
  59.    function is not declared external.  twalk passes them in right to left
  60.    order so ACTION must be declared extern even if it is present in the
  61.    same source file as the routine that calls twalk.
  62.  
  63. Notes:
  64.    Warning:  the ROOTP argument to twalk() is one level of indirection
  65.    less than the ROOTPNTR arguments to tsearch and tdelete.
  66.  
  67. DIAGNOSTICS:
  68.    A NULL pointer is returned by tsearch if there is not enough memory
  69.    available to create a new node.
  70.    A NULL pointer is returned by tsearch and tdelete if ROOTPNTR is NULL
  71.    on entry.
  72.  
  73. BUGS
  74.    Awful things will happen if the calling function alters the pointer to
  75.    the root of a tree.
  76.  
  77.